package com.lwt.codetop.backtracking;

// 22. 括号生成

import java.util.ArrayList;
import java.util.List;

/**
 * 思路：回溯
 * 一个合法的括号序列：优先拼左括号
 *                  左括号数量 < n
 *                  当左括号数量 > 右括号数量时可以拼接右边括号
 * 递归出口 u == 2 * n && leftCnt == rightCnt即为合法括号序列
 */
public class GenerateParentheses{
    public static void main(String[] args) {
        List<String> res = new ArrayList<>();
        dfs(0, 0, 0, 3, "", res);
        System.out.println(res);
    }

    public static void dfs(int u, int left, int right, int n, String curs, List<String> res) {
        if(u == 2 * n){
            if(left == right){
                res.add(curs);
            }
            return;
        }
        // 优先加左括号
        if(left < n) dfs(u + 1, left + 1, right, n, curs + '(', res);
        // 加右括号
        if(left > right) dfs(u + 1, left, right + 1, n, curs + ')', res);
    }
}
